package BackTrackingPackage;

import org.junit.jupiter.api.Test;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @author Lzm
 * @version 1.0
 */
public class combinationSum3_{
  LinkedList<Integer> list = new LinkedList<>();
  List<List<Integer>> result = new ArrayList<>();
  @Test
  public void combinationSum3Test(){
    backTracking(7,3,1);
    System.out.println(result);
  }


  public void backTracking(int n,int k,int startIndex){
    /*剪枝操作*/
    if (ListSum(list) > n) return;
    /*剪枝操作*/
    if (list.size() > k) return;

    /*判断终止条件*/
    if ((list.size() == k) && (ListSum(list) == n)){
      result.add(new ArrayList<>(list));
      return;
    }
    /*剪枝操作*/
    /*这里的i是开始选择元素的位置, 若i = 3, 则表示下一次我们从3开始取
    * i的最大值, maxI表示 i最大为多少, 遍历下去的list能满足长度为k的需要
    * 如 k = 2, 那i最多为8, 若i为9, 那选择9之后, 没有其他元素了, 就不能构成长度为2了
    * 所以在这计算公式为 list.size() + n - maxI == k
    * n - maxI表示从maxI开始选, 还能选 n- maxI个, 如n = 10, 从maxI = 8选, 则还有n-maxI = 2种选择
    * 将下标补齐后maxI = k-(n - list.size()) + 1
    * */
    for (int i = startIndex ; i <= 9  ; i++){
      list.add(i);
      backTracking(n,k,i+1);
      list.removeLast();
    }
  }
  public static int ListSum(List<Integer> list){
    int sum = 0;
    for (Integer num : list) {
      sum += num;
    }
      return sum;
  }
}
